package ArrayAndString;

import java.util.*;


public class ArrayAndString {
    /**
     * 寻找数组的中心索引
     * 给你一个整数数组nums ，请计算数组的 中心下标 。
     * <p>
     * 数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
     * <p>
     * 如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
     * <p>
     * 如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。
     */
    public int pivotIndex(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        int leftSum = 0;
        int rightSum;
        for (int i = 0; i < nums.length; i++) {
            rightSum = sum - nums[i];
            if (leftSum == rightSum) {
                return i;
            }
            leftSum += nums[i];
        }
        return -1;
    }

    /**
     * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
     * <p>
     * 请必须使用时间复杂度为 O(log n) 的算法。
     * <p>

     */
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (target > nums[mid]) {
                left = mid + 1;
            } else if (target < nums[mid]) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        return left;
    }

    /**
     * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
     * <p>
     * 示例 1：
     * <p>
     * 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
     * 输出：[[1,6],[8,10],[15,18]]
     * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
     *
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        int len = intervals.length;
        if (len < 2) {
            return intervals;
        }
        Arrays.sort(intervals, Comparator.comparing(x -> x[0]));
        List<int[]> lastList = new ArrayList<>();
        lastList.add(intervals[0]);
        for (int i = 1; i < len; i++) {
            int[] current = intervals[i];
            int[] last = lastList.get(lastList.size() - 1);
            if (current[0] <= last[1]) {
                last[1] = Math.max(current[1], last[1]);
            } else {
                lastList.add(intervals[i]);
            }
        }
        return lastList.toArray(new int[lastList.size()][]);
    }

    /**
     * 给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。
     * <p>
     * 不占用额外内存空间能否做到？
     * <p>
     * <p>
     * 示例 1:
     * <p>
     * 给定 matrix =
     * [
     * [1,2,3],
     * [4,5,6],
     * [7,8,9]
     * ],
     * <p>
     * 原地旋转输入矩阵，使其变为:
     * [
     * [7,4,1],
     * [8,5,2],
     * [9,6,3]
     * ]
     * [1,2,3],
     * [4,5,6],
     * [7,8,9]
     * <p>
     * [1,4,7],
     * [2,5,8],
     * [3,6,9]
     * <p>
     * [7,4,1],
     * [8,5,2],
     * [9,6,3]
     *
     * @param matrix
     */

    public void rotate(int[][] matrix) {
        int row = matrix.length;
        int column = matrix[0].length;
        //沿着对角线折叠
        for (int i = 0; i < row - 1; i++) {
            for (int j = i + 1; j < column; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        //沿着中间对折
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column / 2; j++) {
                int temp = matrix[i][row - 1 - j];
                matrix[i][row - 1 - j] = matrix[i][j];
                matrix[i][j] = temp;
            }
        }
        System.out.println(matrix);
    }

    /**
     * 零矩阵
     * 编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。
     * <p>
     * 示例 1：
     * <p>
     * 输入：
     * [
     * [1,1,1],
     * [1,0,1],
     * [1,1,1]
     * ]
     * 输出：
     * [
     * [1,0,1],
     * [0,0,0],
     * [1,0,1]
     * ]
     *
     * @param matrix
     */
    public void setZeroes(int[][] matrix) {
        boolean[] row = new boolean[matrix.length];
        boolean[] col = new boolean[matrix[0].length];

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                //找到为零的位置，并做标记
                if (matrix[i][j] == 0) {
                    row[i] = true;
                    col[j] = true;
                }
            }
        }

        for (int i = 0; i < matrix.length; i++) {
            if (row[i]) {
                for (int j = 0; j < matrix[0].length; j++) {
                    matrix[i][j] = 0;
                }
            }
        }

        for (int i = 0; i < matrix[0].length; i++) {
            if (col[i]) {
                for (int j = 0; j < matrix.length; j++) {
                    matrix[j][i] = 0;
                }
            }
        }
    }


    /**
     * 给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * <p>
     * 输入：mat =  [[1,2,3],
     *              [4,5,6],
     *              [7,8,9]]
     * 输出：[1,2,4,7,5,3,6,8,9]
     * <p>
     *
     * @param mat
     * @return
     */
    public int[] findDiagonalOrder(int[][] mat) {
        int row = mat.length;
        int col = mat[0].length;
        int[] result = new int[row * col];
        int k = 0;
        ArrayList<Integer> tempList = new ArrayList<>();
        for (int i = 0; i < row + col - 1; i++) {
            tempList.clear();
            //定义初始位置
            int r = i < col ? 0 : i - col + 1;
            int c = i < col ? i : col - 1;

            while (r < row && c > -1) {
                tempList.add(mat[r][c]);
                r++;
                c--;
            }
            if (i % 2 == 1) {
                Collections.reverse(tempList);
            }
            for (Integer integer : tempList) {
                result[k++] = integer;
            }
        }
        return result;
    }


    /**
     * 编写一个函数来查找字符串数组中的最长公共前缀。
     * <p>
     * 如果不存在公共前缀，返回空字符串""。
     * 示例 1：
     * <p>
     * 输入：strs = ["flower","flow","flight"]
     * 输出："fl"
     * 示例 2：
     * <p>
     * 输入：strs = ["dog","racecar","car"]
     * 输出：""
     * 解释：输入不存在公共前缀。
     *
     * @param strs
     */

    public String longestCommonPrefix(String[] strs) {
        if(strs==null || strs[0].length()==0){
            return "";
        }
        if(strs.length==1){
            return strs[0];
        }

        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < strs[0].length(); i++) {
            Boolean flag = true;
            char ch = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                if(i>=strs[j].length() || strs[j].charAt(i) != ch){
                    flag = false;
                    break;
                }
            }
            if(flag){
                stringBuilder.append(ch);
            }else{
                break;
            }
        }
        return stringBuilder.toString();
    }

    /**
     * 翻转字符串里的单词
     * 给你一个字符串 s ，逐个翻转字符串中的所有 单词 。
     *
     * 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
     *
     * 请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。
     *
     * 说明：
     *
     * 输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
     * 翻转后单词间应当仅用一个空格分隔。
     * 翻转后的字符串中不应包含额外的空格。
     *
     * 示例 1：
     *
     * 输入：s = "the sky is blue"
     * 输出："blue is sky the"
     * 示例 2：
     *
     * 输入：s = " hello world "
     * 输出："world hello"
     * 解释：输入字符串可以在前面或者后面包含多余的空格，但是翻转后的字符不能包括。
     * @param s
     * @return
     */
    public String reverseWords(String s) {
        String[] split = s.trim().split("\\s+");

        Stack<String> stack = new Stack<>();

        for (int i = 0; i < split.length; i++) {
            stack.push(split[i]);
        }
        StringBuilder stringBuilder = new StringBuilder();
        while(!stack.isEmpty()){
            String str = stack.pop();
            stringBuilder.append(" ");
            stringBuilder.append(str);
        }
        return stringBuilder.toString().trim();
    }


    public static void main(String[] args) {
        ArrayAndString arrayAndString = new ArrayAndString();
//        System.out.println(arrayAndString.pivotIndex(new int[]{1, 3, 5, 6}));
//        System.out.println(arrayAndString.searchInsert(new int[]{1, 3, 5, 6}, 2));
        //合并区间
//        int[][] array = new int[][]{{1,3},{2,6},{8,10},{15,18}};
//        ArrayAndString arrayAndString = new ArrayAndString();
//        int[][] merge = arrayAndString.merge(array);
//        for (int i = 0; i < merge.length; i++) {
//            for (int j = 0; j < merge[1].length; j++) {
//                System.out.println(merge[i][j]);
//            }
//        }

        //旋转矩阵
//        ArrayAndString arrayAndString = new ArrayAndString();
//        int[][] array = new int[][]{{1, 0, 3}, {4, 5, 6}, {7, 8, 9}};
//        arrayAndString.rotate(array);

        //零矩阵
//        arrayAndString.setZeroes(array);

        //最长公共前缀
//        String[] strs  = new String[]{"flower","fli"};
//        String s = arrayAndString.longestCommonPrefix(strs);
//        System.out.println(s);


        String str1 = "nihaoksdoksad ";
        String str2 = "ok ";
//        int total = 0;
//        int i=0;
//        while (i<=str1.length()){
//            if (str1.indexOf(str2) > 0) {
//                total++;
//            }
//            i++;
//        }
//        System.out.println(total);
//        System.out.println(count(str1,str2));
//        testFindChar();


        String str = "nihaoksdoksad";
        String s="ok";

        int count= (str.length() - str.replaceAll(s,"").length())/2;
        System.out.println(count);
    }
    public static void testFindChar(){
        String str = "啊！我爱你中国！啊，我爱你故乡";
        //存放每个字符的数组
        String [] strs = new String[str.length()];
        //计数该字符出现了多少次
        int count = 0;
        //先把字符串转换成数组
        for(int i = 0;i<strs.length;i++){
            strs[i] = str.substring(i,i+1);
        }
        //挨个字符进行查找，查找到之后count++
        for(int i = 0;i<strs.length;i++){
            if(strs[i].equals("爱你")){
                count++;
            }
        }

        System.out.println("一共有"+count+"个啊");
    }


    public static int count(String filename, String target) {

        String result = filename;
        int count = 0;
        int index = 0;
        while (true) {
            index = result.indexOf(target, index + 1);
            if (index > 0) {
                count++;
            }else {
                break;
            }
        }
        return count;
    }

}
